#include <iostream>
#include <cmath>
#include <vector>

namespace {

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val, ListNode *next=NULL):val(val),next(next){}
};

ListNode* ReverseList(ListNode *head) {
    ListNode *pre = NULL;
    ListNode *node = NULL;
    while (head) {
        node = head->next;
        head->next = pre;
        pre = head;
        head = node;
    }
    return pre;
}

ListNode* ReverseList2(ListNode *head) {
    // 队尾变成队头
    if (head->next == NULL) return head;
    ListNode *last = ReverseList2(head->next);

    head->next->next = head;
    head->next = NULL;
    return last;
}

ListNode *successor = NULL;
// 翻转前n
ListNode* ReverseListN(ListNode *head, int n) {
    if (n == 1) {
        successor = head->next;
        return head;
    }
    ListNode *last = ReverseListN(head->next, n - 1);

    head->next->next = head;
    head->next = successor;
    return last;
}

// 翻转列表 [m, n]
ListNode* ReverseListD(ListNode *head, int m, int n) {
    if (m == 1) {
        return ReverseListN(head, n);
    }
    head->next = ReverseListD(head->next, m - 1, n - 1);
    return head;
}

void PrintList(const ListNode *head) {
    while(head) {
        std::cout << head->val << ",";
        head = head->next;
    }
    std::cout << std::endl;
}

bool HasCircle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

ListNode* DetectCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

ListNode* MergeList(ListNode *head1, ListNode *head2) {
    if (!head1) return head2;
    if (!head2) return head1;

    // 获取头结点
    ListNode *node = NULL;
    if (head1->val <= head2->val) {
        node = head1;
        head1 = head1->next;
    }
    else {
        node = head2;
        head2 = head2->next;
    }

    ListNode *head = node;
    while (head1 && head2) {
        if (head1->val <= head2->val) {
            node->next = head1;
            node = head1;
            head1 = head1->next;
        }
        else {
            node->next = head2;
            node = head2;
            head2 = head2->next;
        }
    }
    node->next = head1 ? head1 : head2;

    return head;
}

ListNode* MergeList2(ListNode *head1, ListNode *head2) {
    if (!head1) return head2;
    if (!head2) return head1;

    if (head1->val <= head2->val) {
        head1->next = MergeList2(head1->next, head2);
        return head1;
    }
    else {
        head2->next = MergeList2(head1, head2->next);
        return head2;
    }
}

typedef std::vector<ListNode *> VectorList;
// 合并链表数组
ListNode* MergeList3(VectorList &list) {
    int num = list.size();
    if (num == 0) return NULL;
    int interval = 1;
    while (interval < num) {
        int add = interval * 2;
        for (int i=0; i<num-interval; i+=add) {
            list[i] = MergeList(list[i], list[i+interval]);
        }
        interval = add;
    }
    return list[0];
}

ListNode* DelMidNode(ListNode *head) {
    if (!head || !head->next)
        return head;

    if (!head->next->next) {
        ListNode *del = head->next;
        head = head->next;
        delete del;
        return head;
    }

    ListNode *first = head;
    ListNode *second = head->next->next;
    while (second->next && second->next->next) {
        first = first->next;
        second = second->next->next;
    }
    second = first->next;
    first->next = first->next->next;
    delete second;
    return head;
}

ListNode* DelBackNode(ListNode *head, int n) {
    int i = 0;
    ListNode *node = head;
    while(node) {
        i++;
        node = node->next;
    }
    if (i == 0 || i < n)
        return head;

    ListNode *dump = new ListNode(0);
    dump->next = head;
    node = dump;
    i -= n;
    while (i > 0) {
        i--;
        node = node->next;
    }
    ListNode *del = node->next;
    node->next = node->next->next;
    head = dump->next;
    delete del;
    delete dump;
    return head;
}

ListNode* DelNthFromEnd(ListNode *head, int n) {
    ListNode *dump = new ListNode(0);
    dump->next = head;
    ListNode *first = dump;
    for (int i=0; i<n+1 && first; i++) {
        first = first->next;
    }
    ListNode *second = dump;
    while (first) {
        first = first->next;
        second = second->next;
    }
    ListNode *del = second->next;
    second->next = second->next->next;
    head = dump->next;
    delete del;
    delete dump;
    return head;
}

ListNode* DelNth(ListNode *head, int n) {
    if (n < 1) return head;
    ListNode *dump = new ListNode(0);
    dump->next = head;
    ListNode *node = dump;
    while (n > 1 && node) {
        n--;
        node = node->next;
    }
    ListNode *del = node->next;
    node->next = node->next->next;
    head = dump->next;
    delete del;
    delete dump;
    return head;
}

ListNode* DelByRatio(ListNode *head, int a, int b) {
    if (a < 1 || a > b)
        return head;

    int n = 0;
    ListNode *node = head;
    while(node) {
        n++;
        node = node->next;
    }

    n = ceil(float(a * n) / b);
    return DelNth(head, n);
}

ListNode* MakeList(int start, int len) {
    ListNode *list = new ListNode(start);
    ListNode *head = list;
    for (int i=1; i<len; i++) {
        ListNode *node = new ListNode(start+i);
        list->next = node;
        list = node;
    }
    return head;
}

ListNode* MakeListFromArray(int array[], int len) {
    ListNode *head = NULL, *cur = NULL;
    for (int i=0; i<len; i++) {
        ListNode *node = new ListNode(array[i]);
        if (cur) {
            cur->next = node;
            cur = node;
        }
        else {
            head = node;
            cur = node;
        }
    }
    return head;
}

// 是否回文链表
bool IsPalindrome(ListNode* head) {
    if (!head) return false;
    if (!head->next) return true;
    
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *mid = slow->next;
    ListNode *tail = ReverseList(mid);
    slow = head;
    fast = tail;
    bool found = true;
    while (fast) {
        if (slow->val != fast->val) {
            found = false;
            break;
        }
        slow = slow->next;
        fast = fast->next;
    }
    ReverseList(tail);
    return found;
}

typedef std::vector<int> VectorInt;

VectorInt TwoSum(VectorInt nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return VectorInt({left, right});
        }
        else if (sum < target) {
            left++;
        }
        else if (sum > target) {
            right--;
        }
    }
    return VectorInt({-1, -1});
}

void handle() {
    ListNode *list = MakeList(0, 10);
    std::cout << "init list: ";
    PrintList(list);

    // 反转列表
    ListNode *reverseList = ReverseList(list);
    std::cout << "resversed list: ";
    PrintList(reverseList);

    reverseList = ReverseList2(reverseList);
    std::cout << "resversed2 list: ";
    PrintList(reverseList);

    reverseList = ReverseListN(reverseList, 5);
    std::cout << "resversedn list: ";
    PrintList(reverseList);

    reverseList = ReverseListD(reverseList, 6, 10);
    std::cout << "resversedd list: ";
    PrintList(reverseList);

    // 链表是否循环
    bool hasCircle = HasCircle(reverseList);
    std::cout << "list has circle " << hasCircle << std::endl;

    ListNode *tail = reverseList;
    ListNode *start = reverseList;
    int startNum = 3;
    while (tail->next) {
        tail = tail->next;
        if (--startNum > 0) start = start->next;
    }
    tail->next = start;
    start = DetectCycle(reverseList);
    std::cout << "detect cycle " << (start ? start->val : -1) << std::endl;
    std::cout << "list has circle " << HasCircle(reverseList) << std::endl;

    // 合并列表
    ListNode *list1 = MakeList(20, 10);
    ListNode *list2 = MakeList(22, 10);
    std::cout << "list1: ";
    PrintList(list1);
    std::cout << "list2: ";
    PrintList(list2);
    ListNode *mergeList = MergeList(list1, list2);
    std::cout << "mergeList: ";
    PrintList(mergeList);

    // 合并列表(递归)
    ListNode *list3 = MakeList(30, 10);
    ListNode *list4 = MakeList(32, 10);
    std::cout << "list3: ";
    PrintList(list3);
    std::cout << "list4: ";
    PrintList(list4);
    ListNode *mergeList2 = MergeList2(list3, list4);
    std::cout << "mergeList2: ";
    PrintList(mergeList2);

    // 删除倒数第n个
    ListNode *list5 = MakeList(1, 10);
    std::cout << "list5: ";
    PrintList(list5);
    ListNode *list6 = DelBackNode(list5, 1);
    std::cout << "list6: ";
    PrintList(list6);

    // 删除中间节点
    ListNode *list7 = MakeList(1, 10);
    std::cout << "list7: ";
    PrintList(list7);
    ListNode *list8 = DelMidNode(list7);
    std::cout << "list8: ";
    PrintList(list8);

    // 删除倒数第n个,一次循环
    ListNode *list9 = MakeList(1, 1);
    std::cout << "list9: ";
    PrintList(list9);
    ListNode *list10 = DelNthFromEnd(list9, 1);
    std::cout << "list10: ";
    PrintList(list10);

    // 删除第a/b个
    ListNode *list11 = MakeList(1, 10);
    std::cout << "list11: ";
    PrintList(list11);
    ListNode *list12 = DelByRatio(list11, 1, 1);
    std::cout << "list12: ";
    PrintList(list12);

    // 合并多个列表
    VectorList lists = {MakeList(10,10), MakeList(15,5), MakeList(20,8), MakeList(30,3), MakeList(35,10)};
    ListNode *mergedList = MergeList3(lists);
    std::cout << "mergedList: ";
    PrintList(mergedList);

    int array[] = {1,2,2,1};
    ListNode *list13 = MakeListFromArray(array, sizeof(array)/sizeof(int));
    std::cout << "list13: ";
    PrintList(list13);
    std::cout << "IsPalindrom: " << IsPalindrome(list13) << std::endl;
    PrintList(list13);

    VectorInt nums({2,7,11,15});
    nums = TwoSum(nums,9);
    std::cout << nums[0] << "," << nums[1] << std::endl;
}

}

void HandleList() {
    handle();
}


